/*
 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice including the dates of first publication and
 * either this permission notice or a reference to
 * http://oss.sgi.com/projects/FreeB/
 * shall be included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 *
 * Except as contained in this notice, the name of Silicon Graphics, Inc.
 * shall not be used in advertising or otherwise to promote the sale, use or
 * other dealings in this Software without prior written authorization from
 * Silicon Graphics, Inc.
 */
/*
 *
 * OpenGL ES 1.0 CM port of GLU by Mike Gorchak <mike@malva.ua>
*/

#ifndef _MONO_CHAIN_H
#define _MONO_CHAIN_H

#include "directedLine.h"
#include "partitionY.h"

class monoChain;

class monoChain
{
   directedLine* chainHead;
   directedLine* chainTail;
   monoChain* next;
   monoChain* prev;
   monoChain* nextPolygon; // a list of polygons

   // cached informatin
   // bounding box
   Real minX, maxX, minY, maxY;
   Int isIncrease;

   // for efficiently comparing two chains
   directedLine* current;

   public:
      monoChain(directedLine* cHead, directedLine* cTail);
      ~monoChain() {}

      inline  void setNext(monoChain* n) {next = n;}
      inline void setPrev(monoChain* p) {prev = p;}
      inline void setNextPolygon(monoChain* np) {nextPolygon = np;}
      inline monoChain* getNext() {return next;}
      inline monoChain* getPrev() {return prev;}
      inline directedLine* getHead() {return chainHead;}
      inline directedLine* getTail() {return chainTail;}

      inline void resetCurrent() { current=((isIncrease==1)?chainHead:chainTail);}

      void deleteLoop();
      void deleteLoopList();

      // insert a new chain between prev and this
      void insert(monoChain* nc);

      Int numChainsSingleLoop();
      Int numChainsAllLoops();
      monoChain** toArrayAllLoops(Int& num_chains);
      Int toArraySingleLoop(monoChain** array, Int index);

      Int isKey;
      Real keyY; // the current horizotal line
      Real chainIntersectHoriz(Real y); // updates current incrementally for efficiency
      directedLine* find(Real y); // find dline so that y intersects dline.
};

monoChain* directedLineLoopToMonoChainLoop(directedLine* loop);
monoChain* directedLineLoopListToMonoChainLoopList(directedLine* list);
Int MC_sweepY(Int nVertices, monoChain** sortedVertices, sweepRange** ret_ranges);

void MC_findDiagonals(Int total_num_edges, monoChain** sortedVertices,
                      sweepRange** ranges, Int& num_diagonals,
                      directedLine** diagonal_vertices);

directedLine* MC_partitionY(directedLine* polygons, sampledLine** retSampledLines);

#endif /* _MONO_CHAIN_H */
